home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 20 / Cream of the Crop 20 (Terry Blount) (1996).iso / os2 / sysb091a.zip / sysbench / src / pmb_heaps.c < prev    next >
C/C++ Source or Header  |  1994-11-05  |  14KB  |  606 lines
  1. /*-------------------Start heapsort.c program-------------------*/
  2.  
  3. /****************************************************************/
  4. /*                         HEAPSORT                             */
  5. /*                     C Program Source                         */
  6. /*          Heapsort program for variable sized arrays          */
  7. /*                 Version 1.0, 04 Oct 1992                     */
  8. /*             Al Aburto (aburto@marlin.nosc.mil)               */
  9. /*                      ('ala' on BIX)                          */
  10. /*                                                              */
  11. /* Based on the Heap Sort code in 'Numerical Recipes in C' by   */
  12. /* William H. Press, Brian P. Flannery, Saul A. Teukolsky, and  */
  13. /* William T. Vetterling, Cambridge University Press, 1990,     */
  14. /* ISBN 0-521-35465-X.                                          */
  15. /*                                                              */
  16. /* The MIPS rating is based upon the program run time (runtime) */
  17. /* for one iteration and a gcc 2.1 unoptimized (gcc -DUNIX)     */
  18. /* assembly dump count of instructions per iteration for a i486 */
  19. /* machine (assuming 80386 code).  This is the reference used.  */
  20. /*                                                              */
  21. /* The maximum amount of memory allocated is based on the 'imax'*/
  22. /* variable in main(). Memory size = (2000*sizeof(long))*2^imax.*/
  23. /* imax is currently set to 8, but this value may be increased  */
  24. /* or decreased depending upon your system memory limits. For   */
  25. /* standard Intel PC CPU machines a value of imax = 3 must be   */
  26. /* used else your system may crash or hang up despite code in   */
  27. /* the program to prevent this.                                 */
  28. /****************************************************************/
  29.  
  30. /****************************************************/
  31. /* Example Compilation:                             */
  32. /* (1) UNIX Systems:                                */
  33. /*     cc -DUNIX -O heapsort.c -o heapsort          */
  34. /*     cc -DUNIX heapsort.c -o heapsort             */
  35. /****************************************************/
  36.  
  37. #include <stdio.h>
  38. #include <math.h>
  39.  
  40. /***************************************************************/
  41. /* Timer options. You MUST uncomment one of the options below  */
  42. /* or compile, for example, with the '-DUNIX' option.          */
  43. /***************************************************************/
  44. /* #define Amiga       */
  45. /* #define UNIX        */
  46. /* #define UNIX_Old    */
  47. /* #define VMS         */
  48. /* #define BORLAND_C   */
  49. /* #define MSC         */
  50. /* #define MAC         */
  51. /* #define IPSC        */
  52. /* #define FORTRAN_SEC */
  53. /* #define GTODay      */
  54. /* #define CTimer      */
  55. /* #define UXPM        */
  56.  
  57. #ifdef Amiga
  58. #include <exec/types.h>
  59. #include <ctype.h>
  60. #endif
  61.  
  62. #ifdef BORLAND_C
  63. #include <ctype.h>
  64. #include <dos.h>
  65. #endif
  66.  
  67. #ifdef MSC
  68. #include <ctype.h>
  69. #endif
  70.  
  71. static double nulltime,runtime,sta,stb;
  72. extern double dtime(void);
  73. static double emips,hmips,lmips,smips[21];
  74.  
  75. static long bplong,ErrorFlag;
  76.  
  77. static long NLoops[21];
  78.  
  79.  
  80. double pmb_heaps(void)
  81. {
  82.  
  83. long  i,j,k,p,imax;
  84.  
  85. bplong = sizeof(long);
  86.  
  87. /*printf("\n   Heap Sort C Program\n");
  88. printf("   Version 1.0, 04 Oct 1992\n\n");
  89.  
  90. printf("   Size of long (bytes): %d\n\n",bplong);
  91.  
  92. printf("   Array Size    RunTime      Scale    MIPS\n");       
  93. printf("    (bytes)       (sec)\n");
  94. */
  95.                    /* NLoops[] holds number of loops  */
  96.                    /* (iterations) to conduct. Preset */
  97.                    /* to 1 iteration.                 */
  98. for( i=0 ; i<= 20 ; i++)
  99. {
  100.  NLoops[i] = 1;
  101. }
  102.                    /* Predetermine runtime (sec) for  */
  103.                    /* memory size 2000 * sizeof(long),*/
  104.                    /* and 256 iterations. p = 0 means */
  105.                    /* don't print the result.         */
  106. j = 2000;
  107. k = 256;
  108. p = 0;
  109. HSORT(j,k,p);
  110.                    /* Set number of iterations (loops)*/
  111.                    /* based on runtime above --- so   */
  112.                    /* program won't take forever on   */
  113.                    /* the slower machines.            */
  114. i = 8;
  115. if ( runtime > 0.125 ) i = 1;
  116.  
  117. NLoops[0] =  32 * i; 
  118. NLoops[1] =  16 * i; 
  119. NLoops[2] =   8 * i;
  120. NLoops[3] =   4 * i;
  121. NLoops[4] =   2 * i;
  122. NLoops[5] =       i;
  123. NLoops[6] =   i / 2;
  124. NLoops[7] =   i / 4;
  125.  
  126. if ( i == 1 )
  127. {
  128. NLoops[6]  = 1;
  129. NLoops[7]  = 1;
  130. }
  131.                    /* Redo the first run and print    */
  132.                    /* the results.                    */
  133. j = 2000;
  134. k = NLoops[0];
  135. p = 1;
  136. HSORT(j,k,p);
  137.                    /* Save estimated mips result      */
  138. smips[0] = emips;
  139.  
  140. j = 2000;
  141. ErrorFlag = 0;
  142.                    /* Now do it for memory sizes up to */ 
  143.                    /* (2000*sizeof(long)) * (2 ** imax)*/
  144.                    /* where imax determines maximum    */
  145.                    /* amount of memory allocated.      */
  146.                    /* Currently I set imax = 8, so if  */
  147.                    /* sizeof(long) = 4 program will run*/
  148.                    /* from 8000, 16000, ..., and up to */
  149.                    /* 2048000 byte memory size. You can*/
  150.                    /* increase imax, but imax = 8 is   */
  151.                    /* limit for this test program.     */
  152. imax = 7;
  153. for( i=1 ; i<= imax ; i++)
  154. {
  155.    j = 2 * j;
  156.  
  157.    k = NLoops[i];
  158.  
  159.    HSORT(j,k,p);
  160.    smips[i] = emips;
  161.  
  162.    if( ErrorFlag > 0L ) break;
  163.  
  164. }
  165.  
  166. if( ErrorFlag == 2L )
  167. {
  168.   err("Heapsort: Could Not Allocate Memory for Array\n");
  169. }
  170.  
  171. hmips = 0.0;
  172. lmips = 1.0e+06;
  173. for( k = 0; k < i; k++)
  174. {
  175. if( smips[k] > hmips ) hmips = smips[k];
  176. if( smips[k] < lmips ) lmips = smips[k];
  177. }
  178.  
  179. /*printf("\n   Runtime is the average for 1 iteration.\n");
  180. printf("   High MIPS = %8.2lf\n",hmips);
  181. printf("   Low  MIPS = %8.2lf\n\n",lmips);*/
  182.   return (hmips+lmips)/2.0*1.0e6;
  183.  
  184. }                                  /* End of main */
  185.  
  186.  
  187. /*************************/
  188. /*  Heap Sort Program    */
  189. /*************************/
  190.  
  191. static HSORT(m,n,p)
  192. long m,n,p;
  193. {
  194.  
  195. register long *base;
  196. register long i,j,k,l;
  197. register long size;
  198.  
  199. long  iter,msize,iran,ia,ic,im,ih,ir;
  200. long  count,ca,cb,cc,cd,ce,cf;
  201.  
  202. msize = m * bplong;
  203. size  = m - 1;
  204. base  = (long *)malloc((unsigned)msize);
  205.  
  206. ia = 106;
  207. ic = 1283;
  208. im = 6075;
  209. ih = 1001;
  210.  
  211.    ErrorFlag = 0L;
  212.  
  213.    if( !base )
  214.      {
  215.      ErrorFlag = 2L;
  216.      return 0;
  217.      }
  218.  
  219.    sta = dtime();
  220.    stb = dtime();
  221.    nulltime = stb - sta;
  222.    if ( nulltime < 0.0 ) nulltime = 0.0;
  223.  
  224.    count = 0;
  225.    sta = dtime();                       /* Start timing */
  226.    for(iter=1 ; iter<=n ; iter++)       /* Do 'n' iterations */             
  227.  
  228.    {
  229.       iran = 47;                        /* Fill with 'random' numbers */
  230.       for(i=1 ; i<=size ; i++)                      
  231.       {
  232.     iran = (iran * ia + ic) % im;
  233.     *(base+i) = 1 + (ih * iran) / im;
  234.       }
  235.       
  236.       k = (size >> 1) + 1;              /* Heap sort the array */
  237.       l = size;
  238.       ca = 0; cb = 0; cc = 0;
  239.       cd = 0; ce = 0; cf = 0;
  240.  
  241.       for (;;)
  242.       {
  243.       ca++;
  244.     if (k > 1)
  245.     {
  246.        cb++;
  247.        ir = *(base+(--k));
  248.     }
  249.     else
  250.     {  
  251.        cc++;
  252.        ir = *(base+l);
  253.        *(base+l) = *(base+1);
  254.        if (--l == 1)
  255.        {
  256.           *(base+1) = ir;
  257.           goto Done;
  258.        }
  259.     }
  260.  
  261.     i = k;
  262.     j = k << 1;
  263.  
  264.     while (j <= l)
  265.     {
  266.        cd++;
  267.        if ( (j < l) && (*(base+j) < *(base+j+1)) ) ++j;
  268.        if (ir < *(base+j))
  269.        {
  270.           ce++;
  271.           *(base+i) = *(base+j);   
  272.           j += (i=j);
  273.        }
  274.        else 
  275.        {
  276.           cf++;
  277.           j = l + 1;
  278.        }
  279.     }
  280.     *(base+i) = ir;
  281.       } 
  282. Done:   
  283.    count = count + ca;
  284.    }
  285.    stb = dtime();                       /* Stop timing */     
  286.    runtime = stb - sta;
  287.    if ( runtime < 0.0 ) runtime = 0.0;
  288.                     /* Scale runtime per iteration */
  289.    runtime = (runtime - nulltime) / (double)n;
  290.       
  291.    ir = count / n;
  292.    ir = (ir + ca) / 2;
  293.                     /* Estimate MIPS rating */
  294.    emips = 24.0 * (double)size + 10.0 * (double)ir;
  295.    emips = emips + 6.0 * (double)cb + 9.0 * (double)cc;
  296.    emips = emips + 10.0 * (double)cd + 7.0 * (double)ce;
  297.    emips = emips + 4.0 * (double)cf;
  298.    sta   = 1.0e-06 * emips;
  299.    emips = sta / runtime;
  300.  
  301.    if ( p != 0L )
  302.    {
  303. //   printf("   %10ld %10.4lf %10.4lf %7.2lf\n",msize,runtime,sta,emips);
  304.    }
  305. free(base);
  306. return 0;
  307. }
  308.  
  309. /*****************************************************/
  310. /* Various timer routines.                           */
  311. /* Al Aburto, aburto@marlin.nosc.mil, 26 Sep 1992    */
  312. /*                                                   */
  313. /* t = dtime() outputs the current time in seconds.  */
  314. /* Use CAUTION as some of these routines will mess   */
  315. /* up when tim